﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.Extensions.String.PatternMatching {
    
    /// <summary>
    /// This class contains the implementation of the Knuth-Morris-Pratt pattern matching algorithm.
    /// For more information regarding the algorithm visit: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
    /// </summary>
    public static class KnuthMorrisPratt {

        /// <summary>
        /// The implementation of the Knuth-Morris-Pratt algorithm.
        /// </summary>
        /// <param name="text">The text in which the pattern must be searched.</param>
        /// <param name="pattern">The pattern to search for in the text.</param>
        /// <param name="comparisons">The number of comparisons executed by the algorithm.</param>
        /// <returns>The indexes where the pattern appears in the text.</returns>
        public static int[] KnuthMorrisPrattAlgorithmImplementation(this string text, string pattern, out int comparisons) {
            comparisons = 0;
            int zPreProcessingNumberOfComparisons = 0;
            List<int> indexes = new List<int>();

            if (pattern.Length <= text.Length) {
                Dictionary<string, int[]> patternZBoxes = pattern.ZAlgorithmPreprocessing(out zPreProcessingNumberOfComparisons);
                int[] borderSizes = pattern.GetBorderSizes(patternZBoxes);
                int[] offsetBorders = pattern.GetOffsetBorders(patternZBoxes, borderSizes);

                for (int i = 0, j; i < text.Length - pattern.Length + 1; ) {
                    for (j = 0; j < pattern.Length; j++) {
                        comparisons++;

                        if (!text.ElementAt(i + j).Equals(pattern.ElementAt(j))) {      // we have a mismatch
                            i += (j == 0) || ((j - 1) - offsetBorders[j - 1]) == 0
                                    ? 1
                                    : (j - 1) - offsetBorders[j - 1];
                            break;
                        }
                    }

                    if (j == pattern.Length) {      // we have a match
                        indexes.Add(i);
                        i += borderSizes.Last() != 0
                                ? borderSizes.Length - borderSizes.Last()
                                : 1;
                    }
                }
            }

            return indexes.ToArray();
        }

        /// <summary>
        /// A method that calculates the size of the border in the substring of this string that starts in the startingPosition (included) and ends in the endingPosition (included).
        /// </summary>
        /// <param name="text">The string that must be checked.</param>
        /// <param name="startingPosition">The starting position (included) of the substring.</param>
        /// <param name="endingPosition">The ending position (included) of the substring.</param>
        /// <returns>The size of the border in the substring [startingPosition .. endingPosition] of this string, or -1 if the two specified indexes contain invalid values.</returns>
        /// <remarks>If endingPosition &lt; startingPosition then this method switches their values.</remarks>
        public static int GetBorderSize(this string text, int startingPosition, int endingPosition) {
            if (endingPosition < startingPosition) { return text.GetBorderSize(endingPosition, startingPosition); }
            if (startingPosition < 0 || endingPosition > text.Length) { return -1; }

            int numberOfComparisons;
            Dictionary<string, int[]> zBoxes = text.Substring(startingPosition, endingPosition - startingPosition + 1).ZAlgorithmPreprocessing(out numberOfComparisons);
            int[] zArray = zBoxes["z"];
            int[] lArray = zBoxes["l"];

            return lArray.Last() == -1 ? 0 : zArray[lArray.Last()];
        }

        /// <summary>
        /// A method that calculates the size of the border for every substring [0 .. i] of the given text.
        /// </summary>
        /// <param name="text">The string that must be checked.</param>
        /// <returns>The size of the borders of every substring [0..i] - where i &lt; text.length - of the given text.</returns>
        /// <remarks>If the size of the given text is 0 than NULL is returned.</remarks>
        public static int[] GetBorderSizes(this string text) {
            if (text.Length > 0) {
                int numberOfComparisons;
                Dictionary<string, int[]> zBoxes = text.ZAlgorithmPreprocessing(out numberOfComparisons);

                return text.GetBorderSizes(zBoxes);
            }

            return null;
        }

        /// <summary>
        /// A method that calculates the size of the border for every substring [0..i] of the given text.
        /// </summary>
        /// <param name="text">The string that must be checked.</param>
        /// <param name="textZBoxes">The z-boxes of the given string.</param>
        /// <returns>The sizes of the border for every substring [0..i] of the given text.</returns>
        private static int[] GetBorderSizes(this string text, Dictionary<string, int[]> textZBoxes) {
            int[] substringBorderSizes = new int[text.Length];

            for (int i = 1; i < substringBorderSizes.Length; i++) {
                substringBorderSizes[i] = textZBoxes["l"][i] != -1 
                                                ? i - textZBoxes["l"][i] + 1 
                                                : 0;
            }

            return substringBorderSizes;
        }

        /// <summary>
        /// A method that calculates the size of the border for every substring [0..i] of the given text. 
        /// Text[borderSize] must be different from Text[substringSize].
        /// </summary>
        /// <param name="text">The string that must be analyzed.</param>
        /// <returns>The size of the border for every substring [0..i] of the given text.</returns>
        /// <remarks>Text[borderSize] must be differen from Text[substringSize]</remarks>
        public static int[] GetOffsetBorders(this string text) {
            int numberOfComparisons;

            if (text.Length > 0) { return text.GetOffsetBorders(text.ZAlgorithmPreprocessing(out numberOfComparisons)); }

            return null;
        }

        /// <summary>
        /// A method that calculates the size of the border for every substring [0..i] of the given text. 
        /// Text[borderSize] must be different from Text[substringSize].
        /// </summary>
        /// <param name="text">The string that must be analyzed.</param>
        /// <param name="textZBoxes">The result of the Z Preprocessing of the text.</param>
        /// <returns>The size of the border for every substring [0..i] of the given text.</returns>
        private static int[] GetOffsetBorders(this string text, Dictionary<string, int[]> textZBoxes) {
            return text.GetOffsetBorders(textZBoxes, text.GetBorderSizes(textZBoxes));
        }

        /// <summary>
        /// A method that calculates the size of the border for every substring [0..i] of the given text. 
        /// Text[borderSize] must be different from Text[substringSize].
        /// </summary>
        /// <param name="text">The string that must be analyzed.</param>
        /// <param name="textZBoxes">The result of the Z Preprocessing of the text.</param>
        /// <param name="borderSizes">The sizes of the regular borders of the text.</param>
        /// <returns>The size of the border for every substring [0..i] of the given text.</returns>
        private static int[] GetOffsetBorders(this string text, Dictionary<string, int[]> textZBoxes, int[] borderSizes) {
            if (text.Length != textZBoxes["r"].Length || text.Length != borderSizes.Length) { return null; }

            int[] borders = new int[text.Length];

            for (int i = 1; i < text.Length - 1; i++) {
                if (borderSizes[i] != 0) {
                    if (!text.ElementAt(i + 1).Equals(text.ElementAt(borderSizes[i]))) { borders[i] = borderSizes[i]; } 
                    else {
                        for (int j = textZBoxes["l"][i]; j <= i; j++) {
                            if (textZBoxes["z"][j] > 0 && (j + textZBoxes["z"][j]) >= i && !text.ElementAt(i - j + 1).Equals(text.ElementAt(i + 1))) {
                                borders[i] = i - j + 1;
                                break;
                            }
                        }
                    }
                }
            }

            return borders;
        }
    }
}
